/*

Copyright (C) 2008 Victor Manuel Sanchez Cartagena, Juan Antonio Perez Ortiz


This file is part of ANTLRArbol.

ANTLRArbol is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

ANTLRArbol is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/. 

*/

package org.ANTLRArbol.lib;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

/**
 * 
 * Stores information about variables and dependencies between them.
 * It is used by the modified grammar when its associated parser is executed.
 * 
 * @author vitaka
 *
 */
public class DependenciesGraphANTLRArbol {

	/**
	 * 
	 * Represents a dependency between two variables
	 * 
	 * @author vitaka
	 *
	 */
	private class Transition
	{
		/**
		 * If A depends on B, this attribute is A
		 */
		public Variable from;
		
		/**
		 * If A depends on B, this attribute is B
		 */
		public Variable to;
		
		/**
		 * Constructor
		 * @param from Variable that depends on another 
		 * @param to The variable "from" depends on this variable
		 */
		public Transition(Variable from, Variable to) {
			super();
			this.from = from;
			this.to = to;
		}
		
		public boolean equals(Object o)
		{
			boolean retorno = false;
			if(o.getClass().equals(Transition.class))
			{
				Transition t = (Transition) o;
				if(t.from.equals(this.from) && t.to.equals(this.to))
					retorno = true;
			}
			
			return retorno;
		}
	}
	
	/**
	 * 
	 * Represents a unique variable in the dependency graph.
	 * If it's a variable declared in Java, its name is the name used in the declaration.
	 * 
	 * If it's a synthesized or inherited attribute of the current rule, its name starts with "$"
	 * 
	 * If it's a synthesized attribute of another rule, its name is: "[" + name of the node generated by AttributeTreeANTLRArbol + "." + name of the attribute 
	 * We use nameTable to translate the name of the variable in the source code to its name when it is represented by an object of this class.
	 * We do this because different names in the source code can refer to the same variable. For example:
	 * 
	 * rule returns [String s]
	 * :
	 * 		var=another_rule   { $s = $var.attribute; $s = $another_rule.attribute;  }
	 * ;
	 * 
	 * @author vitaka
	 *
	 */
	private class Variable
	{
		/**
		 * Unique name in the same scope
		 */
		public String name;
		public int scope;
		public Variable( String nombre, int ambito) {
			super();
			this.scope = ambito;
			this.name = nombre;
		}
		
	}
	
	/**
	 * 
	 * An entry in the Name Table, used to translate from a variable name in the
	 * source code to the name in the "Variable" class.
	 * 
	 * @author vitaka
	 *
	 */
	private class NameEntry
	{
		/**
		 * Name in the source code
		 */
		public String name;
		public int scope;
		/**
		 * Name in the Variable class
		 */
		public String variable;
		
		/**
		 * 
		 * @param nameSourceCode Name of the variable in the sorce code
		 * @param scope Scope of the variable in the source code
		 * @param variable Name of the variable in the "Variable" class.
		 */
		public NameEntry(String nameSourceCode, int scope, String variable) {
			super();
			this.scope = scope;
			this.name = nameSourceCode;
			this.variable = variable;
		}
		
	}
	
	/**
	 * Nodes of the dependency graph. They are variables.
	 */
	private ArrayList<Variable> nodes;
	
	/**
	 * Transitions of the dependency graph. A transition from A to B means that A depends on B.
	 */
	private HashSet<Transition> transitions;
	
	/**
	 * Table to translate from a variable name in the
	 * source code to the name in the "Variable" class.
	 */
	private ArrayList<NameEntry> nameTable;
	
	
	public DependenciesGraphANTLRArbol() {
		nodes = new ArrayList<Variable>();
		transitions = new HashSet<Transition>();
		nameTable= new ArrayList<NameEntry>();
		//System.out.println("GrafoDependenciasANTLRArbol:Iniciando grafo dependencias");
	}
	
	/**
	 * 
	 * Removes all the variables whose scope number is greater than the parameter
	 * 
	 * @param newScope Number of the new scope.
	 */
	public void scopeExit(int newScope)
	{
		for(int i=nameTable.size()-1;i>=0 && nameTable.get(i).scope>newScope;i--)
		{
			nameTable.remove(i);
		}
		
		for(int i=nodes.size()-1;i>=0 && nodes.get(i).scope>newScope;i--)
		{
			removeVariableTransitions(nodes.get(i));
			nodes.remove(i);
		}	
	}
	
	/**
	 * Removes transitions that start in the variable var. Keeps transitive dependencies. E.g.: if A depends on
	 * on B, B depends on C and we are removing B, it adds a new transition between A and C.
	 * 
	 * @param var Variable where transitions to be removed start.
	 */
	private void removeVariableTransitions(Variable var) {
		
		HashSet<Variable> dependenDirectamente= new HashSet<Variable>();
		
		
		HashSet<Transition> transiciones2 = new HashSet<Transition>(transitions);
		for(Transition t: transiciones2)
		{
			if(t.from==var)
			{
				dependenDirectamente.add(t.to);
				transitions.remove(t);
			}
			
		}
		
		dependenDirectamente.remove(var);
		
		for(Transition t: transiciones2)
		{
			if(t.to==var)
			{
				for(Variable depende: dependenDirectamente)
				{
					transitions.add(new Transition(t.from,depende));
				}
			}
		}		
		
	}
	
	/**
	 * Looks up a variable name in the Name Table.
	 * 
	 * @param name Name of the variable in the source code
	 * @param scope Scope of the variable in the source code
	 * @return String that identifies a variable node in the graph.
	 */
	private String lookupInNameTable(String name, int scope)
	{
		String retorno="";
		
		boolean encontrada=false;
		for(int i=nameTable.size()-1;i>=0 && !encontrada;i--)
		{
			NameEntry e = nameTable.get(i);
			if(e.scope<=scope)
				if(e.name.equals(name))
				{
					retorno=e.variable;
					encontrada=true;
				}
		}
		
		return retorno;
	}
	
	/**
	 *
	 * Looks up a variable in the list of nodes, given its unique name. 
	 * 
	 * @param name Unique name of the variable
	 * @param scope Scope in ten source code
	 * @return A variable object corresponding to the given name.
	 */
	private Variable lookupVariable(String name, int scope)
	{		
		Variable retorno =null;
		String nombreABuscar=name;
		
		if(name.startsWith("$"))
		{
			String [] pedazos = name.split("\\.");
			if(pedazos.length>0)
			{
				String nombreEncontrado = this.lookupInNameTable(pedazos[0], scope);
				if(!nombreEncontrado.isEmpty())
				{
					pedazos[0]="["+nombreEncontrado;
					
					nombreABuscar="";
					for(int i=0; i<pedazos.length; i++)
					{
						nombreABuscar+=pedazos[i];
						if(i<pedazos.length-1)
							nombreABuscar+=".";
					}
				}
			}		
		}
		
		for(int i=nodes.size()-1;i>=0 && retorno==null;i--)
		{
			Variable v = nodes.get(i);
			if(v.scope<=scope)
				if(v.name.equals(nombreABuscar))
					retorno = v;
		}
		return retorno;
	}

	/**
	 * Adds to the graph the attributes of a rule different of the current one.
	 * If the rule is syntactical one, these attributes are its synthesized attributes.
	 * If it's a lexical one, there is only an attribute: text. 
	 * 
	 * @param name1 First name of the rule reference. E.g.:  a_rule 
	 * @param name2 Second name of the rule reference. E.g.: var = a_rule . The first name would be "a_rule" and the second "var". 
	 * @param nodeName Name of the node that represents the last execution of this rule. The name is returned by the method startNotTerminal of AttributeTreeANTLRArbol and passed as a synthesized attribute.
	 * @param attrs Attributes of the rule.
	 * @param scope 
	 */
	public void addVariableANTLR(String name1, String name2, String nodeName, AttributesANTLRArbol attrs, int scope)
	{
		nameTable.add(new NameEntry(name1,scope,nodeName));
		if(!name2.isEmpty())
			nameTable.add(new NameEntry(name2,scope,nodeName));
		
		if(attrs!=null)
		{	
			//La variable representa una regla no terminal
			for(String sin: attrs.sintetizados)
			{
				this.addVariable("["+nodeName+"."+sin, scope);
			}
			
			for(String her: attrs.heredados)
			{
				this.addVariable("["+nodeName+"."+her, scope);
			}
		}
		else
		{
			//La variable representa un terminal
			this.addVariable("["+nodeName+".text", scope);
		}
		
		
	}
	
	/**
	 * Adds a variable to the graph, given its unique name and its scope
	 * 
	 * @param nameVar Unique name (in the same scope) of the variable.
	 * @param scope Scope of the variable
	 */
	public void addVariable(String nameVar, int scope)
	{
		
		Variable nodo= new Variable(nameVar,scope);
		nodes.add(nodo);
		transitions.add(new Transition(nodo,nodo));
	}
	
	/**
	 * Adds a transition to the graph
	 * 
	 * @param from If A depends on B, this is the name in the source code of A
	 * @param to If A depends on B, this is the name in the source code of B
	 * @param scope
	 */
	public void addDependency(String from, String to, int scope)
	{
		Variable vOrigen=this.lookupVariable(from, scope);
		Variable vDestino=this.lookupVariable(to, scope);
		
		
		if(vOrigen!=null && vDestino!=null)
		{
			transitions.add(new Transition(vOrigen,vDestino));
			//System.out.println("GrafoDependenciasANTLRArbol:Añadiendo dependencia: "+origen+" -> "+destino);
		}
		//else
			//System.err.println("ADVERTENCIA: No se ha podido añadir la dependencia \""+origen+" -> "+destino+"\" porque alguno de los 2 nodos no existe");
	}
	
	/**
	 * Removes transitions that start in the variable var.
	 * @param var Name of the variable where transitions to be removed start.
	 * @param scope
	 */
	public void removeDependencies(String var, int scope)
	{
		
		//System.out.println("GrafoDependenciasANTLRArbol:Quitando dependencias: "+var);
		
		Variable vEncontrada= this.lookupVariable(var, scope);	
		
		if(vEncontrada!=null)
		{
			HashSet<Transition> transiciones2 = new HashSet<Transition>(transitions);
			for(Transition t: transiciones2)
			{
				if(t.from.equals(vEncontrada))
					transitions.remove(t);
			}
		}
	}
	
	/**
	 * 
	 * Returns all the variables that depend DIRECTLY on the given one.
	 * 
	 * @param var 
	 * @return
	 */
	private Set<Variable> getAdjacent(Variable var)
	{
		HashSet<Variable> retorno = new HashSet<Variable>();
		
		for(Transition t: transitions)
		{
			if(t.from==var)
				retorno.add(t.to);
		}
		
		return retorno;
	}
	
	/**
	 * Returns all the variables that depend on the given one.
	 * 
	 * @param var Name of the variable in the source code.
	 * @param ambito Scope
	 * @return A Set of variables that depend on the given one.
	 */
	public Set<String> getVariablesThatDepends(String var, int ambito)
	{
		Variable vOrigen = this.lookupVariable(var, ambito);
		HashSet<String> retorno = new HashSet<String>();
		
		if(vOrigen!=null)
		{
			HashSet<Variable> explorados= new HashSet<Variable>();
			
			HashSet<Variable> vivos = new HashSet<Variable>();
			vivos.addAll(getAdjacent(vOrigen));
			
			while(!vivos.isEmpty())
			{
				HashSet<Variable> nuevosVivos = new HashSet<Variable>();
				for(Variable nodoVivo: vivos)
				{
					nuevosVivos.addAll(getAdjacent(nodoVivo));
				}
				nuevosVivos.removeAll(vivos);
				nuevosVivos.removeAll(explorados);
				explorados.addAll(vivos);
				vivos=nuevosVivos;
			}
			
			
			for(Variable v: explorados)
				retorno.add(v.name);
			
		}
		
		return retorno;
	}
	
	
	
}
